﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0207_KSimilarity : IAlgorithm
    {
        // 854. 相似度为 K 的字符串

        /*
        对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
        给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。

        提示：
            1 <= s1.length <= 20
            s2.length == s1.length
            s1 和 s2  只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母
            s2 是 s1 的一个字母异位词
        */

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
        }

        // 算法
        // abcd dcab

        int ans;

        public int KSimilarity(string s1, string s2)
        {
            StringBuilder str1 = new StringBuilder();
            StringBuilder str2 = new StringBuilder();
            for (int i = 0; i < s1.Length; i++)
            {
                if (s1[i] != s2[i])
                {
                    str1.Append(s1[i]);
                    str2.Append(s2[i]);
                }
            }
            if (str1.Length == 0)
            {
                return 0;
            }
            ans = str1.Length - 1;
            DFS(0, 0, str1.Length, str1.ToString(), str2.ToString());
            return ans;
        }

        public void DFS(int pos, int cost, int len, string str1, string str2)
        {
            if (cost > ans) return;
            while (pos < str1.Length && str1[pos] == str2[pos])
                pos++;
            if (pos == str1.Length)
            {
                ans = Math.Min(ans, cost);
                return;
            }
            /* 当前状态的交换次数下限大于等于当前的最小交换次数 */
            if (cost + MinSwap(str1, str2, pos) >= ans) return;
            for (int i = pos + 1; i < str1.Length; i++)
            {
                if (str1[i] == str2[pos])
                {
                    string str1Next = Swap(str1, i, pos);
                    DFS(pos + 1, cost + 1, len, str1Next, str2);
                }
            }
        }

        public int MinSwap(string s1, string s2, int pos)
        {
            int tot = 0;
            for (int i = pos; i < s1.Length; i++)
                tot += s1[i] != s2[i] ? 1 : 0;
            return (tot + 1) / 2;
        }

        public string Swap(string cur, int i, int j)
        {
            char[] arr = cur.ToCharArray();
            (arr[j], arr[i]) = (arr[i], arr[j]);
            return new string(arr);
        }
    }
}
